Referring to FIG. 1, a router 10 is connected to networks 11, 12, 13, and 14 through interfaces 110, 120, 130, and 140, which are, for example, Ethernet cables. In a practical environment, router 10 can route packets through thousands of interfaces to thousands of networks.
Router 10 includes a routing table 15 for recording routing information. The routing information contains status and configurations of routes to which router 10 has access. The routes in routing table 15 can be determined according to a routing protocol, e.g., BGP (Border Gateway Protocol), OSPF (Open Shortest Path First), or RIP (Routing Information Protocol). BGP is an Internet protocol that allows routers across autonomous systems (e.g., company networks or university networks) to share routing information, thereby establishing efficient, loop-free routes. OSPF and RIP are routing protocols that allow routing information to be exchanged by routers within an autonomous system.
Router 10 also includes a routing table manager (RTM) 16 that performs central routing process and manages routing table 15. The central routing process comprises an IP (Internet Protocol) stack that runs router-executable processes, e.g., Unix processes. When a packet arrives at one of the interfaces 110, 120, 130, and 140, router 10 executes processes in the IP stack to perform specified functions according to the type of the packet. If the packet is a data packet, the IP stack selects a route from routing table 15, and forwards the packet according to the route. If the packet is a route update packet, as will be described below, the IP stack executes appropriate protocols to update routing table 15.
A route update packet is submitted to routing table manager 16 when a change occurs in a route accessible by router 10. A change in a route, for example, can be a configuration change in a remote network to which router 10 has access. Such a change can affect how router 10 routes incoming data packets to their respective destinations, and therefore is recorded in routing table 15.
In one scenario, referring to FIG. 1, a change in a route has occurred in a network indicated by a network address 192.32.27.0. In addition to network 192.32.27.0, the routing domain also includes networks 11, 12, and networks 13, 14, respectively.
The change in network 192.32.27.0 is submitted to routing table manager 16 through interfaces 120 and 130. If the change submitted by one interface, e.g., interface 120, arrives before the other interface, e.g., interface 130, routing table manager 16 will update routing table 15 according to the change submitted by interface 120. When another identical change subsequently arrives from interface 130, routing table manager 16 will treat the change as a new update. Routing table manager 16 will compare the later-arrived change with a corresponding entry in routing table 15, keep the one with better performance, and discard the other one.
In certain scenarios, it is desirable to maintain separate routing tables for different address domains. For example, an independent business entity that subscribes to a VPN may want to assure privacy in its network configurations. The VPN is subscribed from an ISP (Internet Service Provider), which includes a router in its backbone network to provide routing service to all of its VPN subscribers. To prevent routing information of one VPN from being seen by another, the ISP can maintain a separate routing table in the router for each VPN subscriber and update the table independently of others.
Referring to FIG. 2, a router 20 includes two routing tables 151 and 152, each for one of the address domains, domain A and domain B. Router 20 is partitioned into two virtual routers 101 and 102, each functioning like a traditional router (e.g., router 10). Each of the virtual routers 101 and 102 maintains a stack, a routing table (151 or 152), and a routing manager (161 or 162). Information received from domain A propagates through an interface 110′ or 120′ to reach routing manager 161 and routing table 151, while information received from domain B propagates through an interface 130′ or 140′ to reach routing manager 162 and routing table 152. Each routing table records routes for one of the address domains. The two routing tables are independently updated, and information in one routing table is not shared with the other.
When a change occurs in a network common to domain A and domain B (e.g., network 197.32.27.0), the change is submitted to routing table managers 161 and 162. The routing table managers receive the change from respective interfaces (120′ and 130′), execute respective IP stacks, and update respective routing tables (151 and 152). Although the use of multiple routing tables and IP stacks ensures privacy in routing information for each address domain, running multiple IP stacks on one physical router 20 nevertheless limits the router's ability to scale.